#include "basic_fun.h"

void insertion_sort(int* array, int count);

int main(void)
{
	int array[10] = {0};
	int array_size = get_array_size(array);
	generate_array(array, array_size);
	do_sort(array, array_size, insertion_sort);
	return 0;
}

void insertion_sort(int* array, int count)
{
       // 将数组分为已排序和未排序两大块
       // 挑选未排序中index最小的n，在已排序的元素中，找到第一个小于等于array[n]的元素坐标未i
       // 把array[n]插入到i+1（原来处于i和n之间的元素，向后诺一格）
	int unsort_start, sort_index;
	for (unsort_start = 1; unsort_start < count; unsort_start++)
	{
		// 将array[unsort_start]保存至临时变量，避免已排序元素向后挪动时覆盖，导致原有数值丢失
		int temp = array[unsort_start];
		sort_index = unsort_start - 1;

		// 得到第一个比array[unsort_index]小的元素坐标
		while ((sort_index >= 0) && (temp < array[sort_index]))
		{
			// 元素后移一格
			array[sort_index + 1] = array[sort_index];
			sort_index--;
		}
		// 如果没有元素比array[unsort_index]小，此时sort_index = -1
		// array[unsort_index]将被放在第一个元素
		array[sort_index + 1] = temp;
	}
}
